//
// Description: 5727. 找出游戏的获胜者
// Created by Loading on 2021/4/11.
//

/* 典型的约瑟夫环问题 */

#include <bits/stdc++.h>

using namespace std;

/* 直接模拟循环 */
int findTheWinner(int n, int k) {
    int out = 0;//出局人数
    int index_k = 0;//k的迭代器
    int index = 0;//数组下标迭代器

    vector<int> vec;
    for (int i = 0; i < n; ++i) {
        vec.emplace_back(i + 1);
    }

    //出局人数 = n - 1，结束循环
    while (out < n - 1) {
        //下标值为-1时说明已出局
        if (vec[index] != -1) {
            ++index_k;
        }
        //迭代至k，数组对应值置为-1，此人出局，重置k的迭代器
        if (index_k == k) {
            vec[index] = -1;
            out++;
            index_k = 0;
        }

        index++;
        //迭代器循环
        if (index == n) {
            index = 0;
        }
    }

    for (int i = 0; i < n; ++i) {
        //唯一不为-1的即为胜利者，编号为下标 + 1
        if (vec[i] != -1) {
            return i + 1;
        }
    }

    return 1;
}

/* 仅定位出局人，使用erase删除元素 */
int findTheWinner2(int n, int k) {
    vector<int> vec;
    for (int i = 0; i < n; ++i) {
        vec.emplace_back(i + 1);
    }

    int index = 0;
    while (vec.size() > 1) {
        //计算将要出局的人的下标
        index = (int) ((index + k - 1) % vec.size());
        ///erase可能较耗时
        vec.erase(vec.begin() + index);
    }

    return vec[0];
}

/* 公式法 */

/*
 * 数学思想：考虑胜利者下标的变化，每次出局一个人，所有人都向前移动k位，包括胜利者
 * 递推公式：F(n, k) = (F(n - 1, k) + k) % n  F(n, k) 表示n个人，每次数到k时删除，最后胜利者的下标（下标从0开始，且n > 1)
 * 可从n开始倒推，假设n个人时，胜利者下标为x，n个人时，出局一人后变为n - 1个人，组成新环，所有人向前移动k位（包括胜利者）,继续推……
 * 直到推到1人，已知1人时，胜利者即为此人，下标为0，带着这个结果，再去正推
 */

int findTheWinner3(int n, int k) {
    int winner = 0;
    for (int i = 2; i <= n; ++i) {
        winner = (winner + k) % i;
    }

    return winner + 1;
}

int main() {
    clock_t starttime = clock();
    cout << findTheWinner(500, 7) << endl;
    clock_t endtime = clock();
    cout << "直接模拟循环耗时：" << (double) (endtime - starttime) / CLOCKS_PER_SEC * 1000 << "毫秒" << endl;

    starttime = clock();
    cout << findTheWinner2(500, 7) << endl;
    endtime = clock();
    cout << "仅定位出局人，使用erase删除元素耗时：" << (double) (endtime - starttime) / CLOCKS_PER_SEC * 1000 << "毫秒" << endl;

    starttime = clock();
    cout << findTheWinner3(500, 7) << endl;
    endtime = clock();
    cout << "公式法耗时：" << (double) (endtime - starttime) / CLOCKS_PER_SEC * 1000 << "毫秒" << endl;
}